import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: wlx
 * Date: 2025-06-22
 * Time: 22:41
 */

// 非递归实现快排
public class quickSort1 {
    public static void quickSort(int[] array) {
        Deque<Integer> stack = new LinkedList<>();
        int left = 0;
        int right = array.length - 1;
        int pivot = partition(array,left,right);
        if (pivot > left + 1) {
            stack.push(left);
            stack.push(pivot - 1);
        }
        if (pivot < right-1) {
            stack.push(pivot+1);
            stack.push(right);
        }
        while (!stack.isEmpty()) {
            right = stack.pop();
            left = stack.pop();
            pivot = partition(array,left,right);
            if (pivot > left + 1) {
                stack.push(left);
                stack.push(pivot - 1);
            }
            if (pivot < right-1) {
                stack.push(pivot+1);
                stack.push(right);
            }
        }
    }

    public static int partition(int[] arr,int left,int right) {
        int tmp = arr[left];

        while(left < right) {
            // 找到比基准tmp小的
            while(left < right && arr[right] >= tmp) {
                right--;
            }
            arr[left] = arr[right];
            // 找到比基准tmp大的
            while(left < right && arr[left] <= tmp) {
                left++;
            }
            arr[right] = arr[left];
        }
        arr[left] = tmp;
        return left;
    }

    public static void main(String[] args) {
        int[] array = {1,4,2,9,6,7};
        quickSort(array);
        System.out.println(Arrays.toString(array));
    }

}
